/**
 * 中文堆数据结构封装 (zh-heap.js)
 * 支持最大堆、最小堆、优先级队列、链式调用
 * 中文方法命名 + JSDoc 参数提示
 */

class 堆 {
  /**
   * 构造函数 - 创建堆数据结构
   * @param {Array} [初始数据=[]] 初始堆元素数组
   * @param {Function} [比较函数=(a,b)=>a-b] 自定义比较函数，默认最小堆
   */
  constructor(初始数据 = [], 比较函数 = (a, b) => a - b) {
    this._数据 = [...初始数据];
    this._比较函数 = 比较函数;
    
    // 构建堆
    if (this._数据.length > 0) {
      this._构建堆();
    }
  }

  /**
   * 获取堆数据数组的副本
   * @returns {Array} 堆数据的副本数组
   */
  取值() {
    return [...this._数据];
  }

  /**
   * 获取堆中元素数量
   * @returns {number} 堆的大小
   */
  大小() {
    return this._数据.length;
  }

  /**
   * 判断堆是否为空
   * @returns {boolean} 堆是否为空
   */
  是否为空() {
    return this._数据.length === 0;
  }

  /**
   * 清空堆中的所有元素
   * @returns {堆} 返回this以支持链式调用
   */
  清空() {
    this._数据 = [];
    return this;
  }

  /**
   * 查看堆顶元素但不移除
   * @returns {*} 堆顶元素
   */
  查看堆顶() {
    return this._数据[0];
  }

  /**
   * 向堆中插入一个元素
   * @param {*} 元素 要插入的元素
   * @returns {堆} 返回this以支持链式调用
   */
  插入(元素) {
    this._数据.push(元素);
    this._上浮(this._数据.length - 1);
    return this;
  }

  /**
   * 批量插入多个元素
   * @param {Array} 元素数组 要插入的元素数组
   * @returns {堆} 返回this以支持链式调用
   */
  批量插入(元素数组) {
    for (const 元素 of 元素数组) {
      this.插入(元素);
    }
    return this;
  }

  /**
   * 移除并返回堆顶元素
   * @returns {*} 堆顶元素，如果堆为空则返回undefined
   */
  弹出堆顶() {
    if (this.是否为空()) {
      return undefined;
    }
    
    const 堆顶 = this._数据[0];
    const 最后元素 = this._数据.pop();
    
    if (this._数据.length > 0) {
      this._数据[0] = 最后元素;
      this._下沉(0);
    }
    
    return 堆顶;
  }

  /**
   * 替换堆顶元素并调整堆
   * @param {*} 元素 新的堆顶元素
   * @returns {*} 被替换的旧堆顶元素
   */
  替换堆顶(元素) {
    if (this.是否为空()) {
      this.插入(元素);
      return undefined;
    }
    
    const 旧堆顶 = this._数据[0];
    this._数据[0] = 元素;
    this._下沉(0);
    return 旧堆顶;
  }

  /**
   * 更新指定索引位置的元素
   * @param {number} 索引 元素索引
   * @param {*} 新元素 新的元素值
   * @returns {堆} 返回this以支持链式调用
   */
  更新元素(索引, 新元素) {
    if (索引 < 0 || 索引 >= this._数据.length) {
      return this;
    }
    
    const 旧元素 = this._数据[索引];
    this._数据[索引] = 新元素;
    
    // 根据新旧元素的比较结果决定上浮还是下沉
    if (this._比较函数(新元素, 旧元素) < 0) {
      this._上浮(索引);
    } else {
      this._下沉(索引);
    }
    
    return this;
  }

  /**
   * 移除指定索引位置的元素
   * @param {number} 索引 元素索引
   * @returns {*} 被移除的元素，如果索引无效则返回undefined
   */
  移除元素(索引) {
    if (索引 < 0 || 索引 >= this._数据.length) {
      return undefined;
    }
    
    const 移除的元素 = this._数据[索引];
    const 最后元素 = this._数据.pop();
    
    if (索引 < this._数据.length) {
      this._数据[索引] = 最后元素;
      // 调整堆
      if (this._比较函数(最后元素, 移除的元素) < 0) {
        this._上浮(索引);
      } else {
        this._下沉(索引);
      }
    }
    
    return 移除的元素;
  }

  /**
   * 查找指定元素在堆中的索引
   * @param {*} 元素 要查找的元素
   * @param {Function} [相等函数=(a,b)=>a===b] 自定义相等比较函数
   * @returns {number} 元素索引，未找到则返回-1
   */
  查找元素(元素, 相等函数 = (a, b) => a === b) {
    for (let i = 0; i < this._数据.length; i++) {
      if (相等函数(this._数据[i], 元素)) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 创建当前堆的深拷贝
   * @returns {堆} 新的堆实例
   */
  克隆() {
    return new 堆(this._数据, this._比较函数);
  }

  /**
   * 将堆转换为有序数组
   * @returns {Array} 排序后的数组
   */
  排序() {
    const 排序数组 = [];
    const 克隆堆 = this.克隆();
    
    while (!克隆堆.是否为空()) {
      排序数组.push(克隆堆.弹出堆顶());
    }
    
    return 排序数组;
  }

  /**
   * 将堆转换为字符串
   * @param {string} [分隔符=', '] 元素分隔符
   * @returns {string} 转换后的字符串
   */
  转字符串(分隔符 = ', ') {
    return this._数据.join(分隔符);
  }

  /**
   * 遍历堆中所有元素
   * @param {Function} 回调 遍历回调函数，接收(元素,索引,数组)参数
   * @returns {堆} 返回this以支持链式调用
   */
  遍历(回调) {
    for (let i = 0; i < this._数据.length; i++) {
      回调(this._数据[i], i, this._数据);
    }
    return this;
  }

  /**
   * 验证当前数据结构是否满足堆的性质
   * @returns {boolean} 是否是有效的堆
   */
  验证堆() {
    for (let i = 0; i < this._数据.length; i++) {
      const 左子节点 = 2 * i + 1;
      const 右子节点 = 2 * i + 2;
      
      if (左子节点 < this._数据.length && this._比较函数(this._数据[左子节点], this._数据[i]) < 0) {
        return false;
      }
      
      if (右子节点 < this._数据.length && this._比较函数(this._数据[右子节点], this._数据[i]) < 0) {
        return false;
      }
    }
    
    return true;
  }

  /**
   * 获取堆的高度（层数）
   * @returns {number} 堆的高度
   */
  获取高度() {
    if (this.是否为空()) return 0;
    return Math.floor(Math.log2(this._数据.length)) + 1;
  }

  /**
   * 获取指定层级的所有元素
   * @param {number} 层级 层级索引（从0开始）
   * @returns {Array} 该层级的元素数组
   */
  获取层级(层级) {
    const 开始索引 = Math.pow(2, 层级) - 1;
    const 结束索引 = Math.min(Math.pow(2, 层级 + 1) - 1, this._数据.length);
    
    return this._数据.slice(开始索引, 结束索引);
  }

  /**
   * 在堆数据上执行自定义操作
   * @param {Function} 操作 接收数据数组的操作函数
   * @returns {堆|*} 新的堆实例或操作结果
   */
  执行(操作) {
    const 结果 = 操作(this._数据);
    if (Array.isArray(结果)) {
      return new 堆(结果, this._比较函数);
    }
    return this;
  }

  /**
   * 内部方法：上浮操作
   * @private
   * @param {number} 索引 需要上浮的元素索引
   */
  _上浮(索引) {
    let 当前索引 = 索引;
    const 当前元素 = this._数据[当前索引];
    
    while (当前索引 > 0) {
      const 父索引 = Math.floor((当前索引 - 1) / 2);
      const 父元素 = this._数据[父索引];
      
      if (this._比较函数(当前元素, 父元素) >= 0) {
        break;
      }
      
      this._数据[当前索引] = 父元素;
      当前索引 = 父索引;
    }
    
    this._数据[当前索引] = 当前元素;
  }

  /**
   * 内部方法：下沉操作
   * @private
   * @param {number} 索引 需要下沉的元素索引
   */
  _下沉(索引) {
    let 当前索引 = 索引;
    const 当前元素 = this._数据[当前索引];
    const 大小 = this._数据.length;
    
    while (true) {
      let 最小索引 = 当前索引;
      const 左子节点 = 2 * 当前索引 + 1;
      const 右子节点 = 2 * 当前索引 + 2;
      
      if (左子节点 < 大小 && this._比较函数(this._数据[左子节点], this._数据[最小索引]) < 0) {
        最小索引 = 左子节点;
      }
      
      if (右子节点 < 大小 && this._比较函数(this._数据[右子节点], this._数据[最小索引]) < 0) {
        最小索引 = 右子节点;
      }
      
      if (最小索引 === 当前索引) {
        break;
      }
      
      this._数据[当前索引] = this._数据[最小索引];
      当前索引 = 最小索引;
    }
    
    this._数据[当前索引] = 当前元素;
  }

  /**
   * 内部方法：构建初始堆结构
   * @private
   */
  _构建堆() {
    for (let i = Math.floor(this._数据.length / 2) - 1; i >= 0; i--) {
      this._下沉(i);
    }
  }

  /**
   * 迭代器实现 - 按堆顶弹出顺序迭代
   * @yields {*} 堆中的元素
   */
  *[Symbol.iterator]() {
    // 默认按堆顶弹出顺序迭代
    const 克隆堆 = this.克隆();
    while (!克隆堆.是否为空()) {
      yield 克隆堆.弹出堆顶();
    }
  }

  /**
   * 层级遍历迭代器 - 按存储顺序迭代
   * @yields {*} 堆中的元素
   */
  *层级迭代() {
    for (const 元素 of this._数据) {
      yield 元素;
    }
  }

  /** 静态方法 */

  /**
   * 静态方法：创建最小堆
   * @static
   * @param {Array} [初始数据=[]] 初始数据数组
   * @returns {堆} 最小堆实例
   */
  static 创建最小堆(初始数据 = []) {
    return new 堆(初始数据, (a, b) => a - b);
  }

  /**
   * 静态方法：创建最大堆
   * @static
   * @param {Array} [初始数据=[]] 初始数据数组
   * @returns {堆} 最大堆实例
   */
  static 创建最大堆(初始数据 = []) {
    return new 堆(初始数据, (a, b) => b - a);
  }

  /**
   * 静态方法：创建优先队列
   * @static
   * @param {Function} 优先函数 优先级比较函数
   * @param {Array} [初始数据=[]] 初始数据数组
   * @returns {堆} 优先队列实例
   */
  static 创建优先队列(优先函数, 初始数据 = []) {
    return new 堆(初始数据, 优先函数);
  }

  /**
   * 静态方法：从数组创建堆
   * @static
   * @param {Array} 数组 源数组
   * @param {Function} [比较函数=(a,b)=>a-b] 自定义比较函数
   * @returns {堆} 堆实例
   */
  static 从数组(数组, 比较函数 = (a, b) => a - b) {
    return new 堆(数组, 比较函数);
  }

  /**
   * 静态方法：判断对象是否是堆实例
   * @static
   * @param {*} 对象 要检查的对象
   * @returns {boolean} 是否是堆实例
   */
  static 是堆(对象) {
    return 对象 instanceof 堆;
  }

  /**
   * 静态方法：堆排序算法
   * @static
   * @param {Array} 数组 要排序的数组
   * @param {Function} [比较函数=(a,b)=>b-a] 排序比较函数
   * @returns {Array} 排序后的数组
   */
  static 堆排序(数组, 比较函数 = (a, b) => b - a) {
    const 堆实例 = new 堆(数组, 比较函数);
    const 结果 = [];
    
    while (!堆实例.是否为空()) {
      结果.push(堆实例.弹出堆顶());
    }
    
    return 结果;
  }
}



// CommonJS 导出

  module.exports = {
    堆,
    default: 堆
  };
  module.exports.堆 = 堆;


// ES 模块导出
// export { 堆 };
// export default 堆;